960F - Pathwalks - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define ll long long

vector<map<ll, ll>> mp;

ll get(ll x, ll w)
{
    auto it = mp[x].lower_bound(w);

    if(it == mp[x].begin()) 
        return 1;
    
    it--;
    return it->second + 1; 
}

void solve()
{
    ll n, m;
    cin >> n >> m;

    mp.resize(n+1);
    ll answer = 0;
 
    for (ll i = 0; i < m; i++)
    {
        ll a, b, w;
        cin >> a >> b >> w;

        ll val = get(a, w);
        if(get(b, w + 1) > val)
            continue;
        
        mp[b][w] = max(mp[b][w], val);
        auto it = mp[b].upper_bound(w);
        
        while(it != mp[b].end() && it->second <= val)
        {
            it = mp[b].erase(it);
        }

        answer = max(answer,val);
    }

    cout << answer << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}/*1691053055.4208179*/